1. Field of the Invention
The invention relates to electronic design automation, and in particular to a system and method for accurately extracting wide elements from a physical layout.
2. Related Art
An electronic design automation (EDA) system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates (“synthesizes”) this high-level design language description into netlists of various levels of abstraction. A netlist describes the IC design and is composed of nodes (functional elements) and edges, e.g., connections between nodes. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives.
The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific (characterized) cell library that has gate-specific models for each cell (i.e., a functional element, such as an AND gate, an inverter, or a multiplexer). The models define performance parameters for the cells; e.g., parameters related to the operational behavior of the cells, such as power consumption, delay, and noise. The netlist and cell library are typically stored in computer readable media within the EDA system and are processed and verified using many well-known techniques.
FIG. 1 shows a simplified representation of an exemplary digital ASIC design flow. At a high level, the process starts with the product idea (step E100) and is realized in an EDA software design process (step E110). When the design is finalized, it can be taped-out (event E140). After tape out, the fabrication process (step E150) and packaging and assembly processes (step E160) occur resulting, ultimately, in finished chips (result E170).
The EDA software design process (step E110) is actually composed of a number of steps E112-E130, shown in linear fashion for simplicity. In an actual ASIC design process, the particular design might have to go back through steps until certain tests are passed. Similarly, in any actual design process, these steps may occur in different orders and combinations. This description is therefore provided by way of context and general explanation rather than as a specific, or recommended, design flow for a particular ASIC.
A brief description of the component steps of the EDA software design process (step E110) will now be provided. During system design (step E112), the designers describe the functionality that they want to implement and can perform what-if planning to refine functionality, check costs, etc. Hardware-software architecture partitioning can occur at this stage. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Model Architect, Saber, System Studio, and DesignWare® products.
During logic design and functional verification (step E114), the VHDL or Verilog code for modules in the system is written and the design is checked for functional accuracy. More specifically, does the design as checked to ensure that produces the correct outputs. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include VCS, VERA, DesignWare®, Magellan, Formality, ESP and LEDA products.
During synthesis and design for test (step E116), the VHDL/Verilog is translated to a netlist. The netlist can be optimized for the target technology. Additionally, the design and implementation of tests to permit checking of the finished chip occurs. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Design Compiler®, Physical Compiler, Test Compiler, Power Compiler, FPGA Compiler, Tetramax, and DesignWare® products.
During design planning (step E118), an overall floorplan for the chip is constructed and analyzed for timing and top-level routing. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Jupiter and Floorplan Compiler products.
During netlist verification (step E120), the netlist is checked for compliance with timing constraints and for correspondence with the VHDL/Verilog source code. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include VCS, VERA, Formality and PrimeTime products.
During physical implementation (step E122), placement (positioning of circuit elements) and routing (connection of the same) is performed. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the Astro product.
During analysis and extraction (step E124), the circuit function is verified at a transistor level, this in turn permits what-if refinement. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include Star RC/XT, Raphael, and Aurora products.
During physical verification (step E126), various checking functions are performed to ensure correctness for manufacturing, electrical issues, lithographic issues, and circuitry. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the Hercules product.
During resolution enhancement (step E128), geometric manipulations of the layout are performed to improve manufacturability of the design. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the iN-Phase, Proteus, and AFGen products.
Finally, during mask data preparation (step E130), the “tape-out” data for production of masks for lithographic use to produce finished chips is performed. Exemplary EDA software products from Synopsys, Inc. that can be used at this step include the CATS(R) family of products.
As indicated in FIG. 1, physical verification of a design (step E126, indicated by the bolded chevron) is performed towards the end of the EDA software design process. A critical aspect of physical verification for modern circuits is the extraction of “wide” elements from the physical layout. Wide elements are those elements that exceed a certain threshold width(s), and therefore require different handling by layout tools. For example, wide metal elements such as interconnects often require increased spacing form adjacent elements to ensure proper formation during subsequent lithographic operations. Other reasons for special handling of wide metal elements can include mechanical stress (requiring slotting of wide metal elements) and scaling effects (resulting from different sets of design rules for different critical dimensions).
Various methods are currently employed to extract wide element information from the polygons in a physical layout. For example, FIG. 2 shows a conventional wide metal extraction method based on the detection of edges that exceed a threshold width W. In FIG. 2, an E-shaped polygon 210 is depicted that includes edges 211-218. Edges 211, 212, and 213 are all greater than threshold width W, and are therefore flagged as being “wide”. However, edges 214-218 all have a length B that is less than threshold width W, and are therefore not flagged as being wide, even though those edges represent portions of element 210 that are, in fact, wide (e.g., the width of element 210 between edges 212 and 217 is greater than threshold width W). Thus, conventional edge extraction techniques such as depicted in FIG. 2 are inappropriate for the more complex polygon shapes common in modern circuit designs.
FIG. 3A shows another conventional wide metal extraction technique in which a detection square 300 is used to identify wide elements in a physical layout 390. Physical layout 390 includes sample polygons 310 and 320. To perform the “square containment” technique, detection square 300 is defined to have edges equal to the threshold width W. Any portions of a layout polygon that can fully contain detection square 300 are then flagged as wide regions. For example, detection square 300 can never fit completely within sample polygon 310. Therefore, polygon 310 would not be flagged as a wide element. On the other hand, the interior region of sample polygon 320 can be fully mapped by detection squares 300. Therefore, the entirety of polygon 320 is flagged as a wide element.
However, because the coverage area of a detection square (e.g., detection square 300) is dependent on the rotational orientation of the detection square, the square containment method can have problems with non-rectangular polygons and polygons not aligned with any of the detection square orientations. For example, FIG. 3B shows a sample polygon 330 having an octagonal shape. Two detection squares 300A and 330B are used to perform a square containment operation on polygon 330. Detection squares 300A and 300B are rotated 45° relative to one another, and each only fits within polygon 330 at a single location. Consequently, regions 330A-33H (shaded) of polygon 330 are not flagged as being wide, resulting in a star-shaped “wide element” (unshaded area) that does not properly represent the full extent of wide polygon 330. Thus, the conventional square containment method also exhibits problematic under-extraction of wide elements.
FIG. 4A shows another conventional wide metal extraction technique in which a polygon is downsized and then upsized to reduce or eliminate small features in the original polygon that could interfere with proper wide area extraction. For example, in FIG. 4A, an E-shaped original polygon 410 is downsized into an intermediate polygon 420. Note that this downsizing operation causes the “legs” of polygon 410 to disappear, so that a subsequent upsizing operation results in a final polygon 430 that exhibits a simple rectangular outline that more accurately captures the extent of the wide regions of original polygon 410.
However, in many cases, the downsizing/upsizing technique can remove important topological information from the original polygon. For example, in FIG. 4B, an octagonal original polygon 440 is downsized into an intermediate polygon 450, resulting in the removal of the “cut corners” of original polygon 440. Therefore, intermediate polygon 450 is upsized back into a final polygon 460 that exhibits a rectangular outline that extends out (in the corner regions) beyond the original outline of original polygon 440. This additional area of polygon 460 can result in problematic over-extraction of wide element information that can in turn impose unnecessary layout modification in adjacent elements.
FIG. 5A shows another conventional wide metal extraction technique in which projected edges are used to trim away non-wide regions of a polygon. For example, FIG. 5A shows a polygon 500 that includes edges E501-E504. Edges E501 and E502 form an acute angle A5 (edges forming obtuse angles are generally considered to represent wide regions by definition). Therefore, a projected edge P501 having length equal to a threshold width W can be created between edge E501 and E502 by constructing an edge perpendicular to edge E501 that hits edge E502. In a similar manner, a projected edge P502 having length equal to threshold width W can be created between edge E502 and E501 by constructing an edge perpendicular to edge E502 that hits edge E501. A region R51 (shaded) defined by the intersection of edges E501 and E502 and projected edges P501 and P502, which represents a non-wide portion of polygon 500, can then be trimmed from polygon 500. This edge projection and subsequent trimming operation can then be iteratively repeated until, in theory, all the non-wide portions of polygon 500 are trimmed away.
Unfortunately, this projected edge technique can result in under-extraction of wide regions due to what is sometimes referred to as “avalanching”. Avalanching takes place when new edges formed by the trimming operation (to remove non-wide regions) can themselves generate new projected edges that trim away more and more of the polygon, until little or none of the original polygon remains. For example, FIG. 5B shows a modified polygon 500′ that includes edges E501′, E502′, E503, E504, E505, and E506, with edges E505 and E506 having been generated by the edge projection/trimming operation applied to polygon 500 in FIG. 5A. Performing the same edge projection/trimming operation on modified polygon 500′ would result in the subsequent trimming of regions R52, R53, and R54, thereby resulting in none of original polygon 500 being identified as being wide.
Accordingly, it is desirable to provide a system and method for wide element extraction from a physical layout that avoids the problematic over-extraction and under-extraction effects demonstrated by conventional methods.